#include<stdio.h>
#include "Linklist.h"
#include <stdlib.h>

struct node *creat_high_list()
{
    Datatype num;
    PNode pnew = NULL;
    PNode first = NULL;
    PNode last = NULL;
    while(1)
    {
        //1.获取数据，创建链表
		
        scanf("%d",&num);
        if(num == 0)
        {
            break;
        }
        pnew = (PNode)malloc(sizeof(*pnew));//强制转换大小
        pnew->data = num;
        pnew->next = NULL;
        //从无到有
        if(first == NULL)
        {
            first = pnew;
            last = pnew;
        }
        else//从少到多
        {
            //三种可能性
            if(pnew->data<=first->data)//插入的pnew->data最小
            {
                //头插法
                pnew->next = first;
                first = pnew;
            }
            else if(pnew->data>=last->data)//插入的pnew->data最大
            {
                //尾插法
                last->next = pnew;
                last = pnew;
            }
            else//插入的pnew->介于两者间
            {
                //查找要插入的位置，要使用两个遍历指针
                PNode p = first;
                PNode pre = p;
                while(1)//遍历一遍
                {
                    if(p->data > pnew->data)
                    break;
                    pre = p;
                    p = p->next;
                }
                pre->next = pnew;// pre < pnew < p
                pnew->next = p;//插入位置
            }
            
        }
    }
    return first;
}

/*----------------------------------------------------*/





/*-------------------------------------------------------------*/




/*---------------------------------------------------------------*/
void printf_list(PNode list)
{
    while(list)
    {
        printf("%d [",list->data);
        list = list->next;
    }
    printf("\n");
}

/*---------------------------------------------------------------*/

void deletelist(PNode l)
{
	PNode p = l;
	while(p)
	{
		l = l->next;
		free(p);
		p = l;
	}
}